package java学习.代码随想录.动态规划.背包;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/13 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 分割等和子集 {
    /**
     * 1. 得到数组的平均值n，看是否存在元素=n ，若
     *
     *
     */
    public static boolean canPartition1(int[] nums) {
        boolean result = false;
        if (nums.length==0||nums==null){
            return result;
        }
        Arrays.sort(nums);
        double sum =0;
        for (int i = 0; i < nums.length; i++) {
           sum+=nums[i];
        }

            if (sum/2==nums[nums.length-1]){
                result = true;
            }
        System.out.println(sum/2);
        System.out.println(Arrays.toString(nums));
        return result;
    }

    public static void main(String[] args) {
//        int []test = {1,1,1,1};
//        int []test = {1,5,11,5};
        int []test = {3,3,3,4,5};

        System.out.println(canPartition(test));
    }
    /**
     * (1) 背包重量j:    物品对应重量w:    物品价值v:
     * (2) 物品是否 可 重复放入? (是否01?)
     * (3) dp[j] 含义?
     *
     * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * 即： 存在 其中的数字组成 sum/2 ，
     * (1) j: sum/2  w = v = 数值
     * (2) 01背包，不重复放入
     * (3) dp[j] 含义：在重量为j的背包放入 的 数值 = sum/2
     *
     * 1. dp[j] 代表 容量为j 的最大价值
     * 2. dp[j] = max(dp[i],dp[j-w[i]]+v[i])
     * 3. j倒序遍历
     */
    public static boolean canPartition(int[] nums) {
        boolean result = false;
        if (nums.length == 0 || nums == null) {
            return result;
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {
            return result;
        } else {
            int bagw = sum / 2;
            int[] dp = new int[bagw + 1];
            for (int i = 0; i < nums.length; i++) {
                for (int j =  bagw; j >=nums[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }
            System.out.println(Arrays.toString(dp));
            if (dp[bagw] == sum / 2) {
                result = true;
            }
            return result;
        }
    }
/**
 * 班次维护 值班班次维护 dutyMaintain
 */
}
